package competition;

import java.time.zone.ZoneOffsetTransitionRule;
import java.util.*;
import java.util.concurrent.BlockingDeque;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: competition
 * @Author: 江岸
 * @CreateTime: 2021-05-01 22:30
 * @Description:
 */
public class TwiceWeek51 {

    public String replaceDigits(String s) {
        char[] arr = s.toCharArray();
        for (int i=1;i<arr.length;i=i+2){
            int num = arr[i]-'0';
            arr[i] = (char) (arr[i-1] + num);
        }
        StringBuilder sb = new StringBuilder();
        for (char c:arr){
            sb.append(c);
        }
        return sb.toString();
    }

    public int maximumElementAfterDecrementingAndRearranging2(int[] arr) {
         Arrays.sort(arr);
         if (arr[0] > 1) arr[0]=1;
         for(int i=1;i<arr.length;i++){
             if (arr[i]>arr[i-1]) arr[i] = arr[i-1]+1;
         }
         return arr[arr.length];
    }

    public int[] closestRoom(int[][] rooms, int[][] queries) {
        LinkedHashMap<Integer, List<Integer>> map = new LinkedHashMap<>();
        for (int i=0;i<rooms.length;i++){
            int c = i;
            //根据面积分组
           map.computeIfAbsent(rooms[i][1],k->new ArrayList<>()).add(rooms[c][0]);
        }
        ArrayList<Integer> res = new ArrayList<>();
        for (int i=0;i<queries.length;i++){
            TreeSet<Integer> treeSet = new TreeSet<>();
            //添加
            for (Map.Entry<Integer,List<Integer>> entry:map.entrySet()){
                if (entry.getKey()>=queries[i][1]){
                    treeSet.addAll(entry.getValue());
                }
            }
            //查询
            if (!treeSet.isEmpty()){
                if (treeSet.contains(queries[i][0])){
                    res.add(queries[i][0]);
                }else {
                    Integer lower = treeSet.lower(queries[i][0]);
                    Integer higher = treeSet.higher(queries[i][0]);
                    if (lower==null && higher ==null){
                        res.add(-1);
                    }else if (lower==null){
                        res.add(higher);
                    }else if (higher==null){
                        res.add(lower);
                    }else {
                        res.add(Math.abs(queries[i][0]-lower)<=Math.abs(queries[i][0]-higher)?lower:higher);
                    }
                }
            }else {
                res.add(-1);
            }
        }
        //返回
        int[] ints = new int[res.size()];
        for (int i=0;i<ints.length;i++){
            ints[i] = res.get(i);
        }
        return ints;
    }

    public int[] closestRoom2(int[][] rooms, int[][] queries) {
        int[][] q=new int[queries.length][3];
        for(int i=0;i<q.length;i++){
            q[i][0]=queries[i][0];
            q[i][1]=queries[i][1];
            q[i][2]=i;//记录坐标
        }
        //都是通过面积从小到大排序
        Arrays.sort(q,(x,y)->y[1]-x[1]);
        Arrays.sort(rooms,(x,y)->y[1]-x[1]);
        TreeSet<Integer> set=new TreeSet<>();
        int idx=0;//循环加入set的记录坐标
        int[] ans=new int[q.length];
        Arrays.fill(ans,-1);
        for(int i=0;i<q.length;i++){
            while(idx<rooms.length&&rooms[idx][1]>=q[i][1]){
                set.add(rooms[idx][0]);
                idx+=1;
            }
            Integer a=set.floor(q[i][0]);//小于等于
            Integer b=set.ceiling(q[i][0]);//大于等于
            if(a==null&&b==null){
                ans[q[i][2]]=-1;
            }else if(b==null||a==null){
                ans[q[i][2]]=(a==null)?b:a;
            }else{
                ans[q[i][2]]=((q[i][0]-a)<=(b-q[i][0]))?a:b;
            }
        }
        return ans;
    }


}
class SeatManager {

    boolean[] arr;
    int min = 0;

    public SeatManager(int n) {
        arr = new boolean[n];
    }

    public int reserve() {
        int index = min;
        arr[index] = true;
        for (int i=min+1;i<arr.length;i++){
            if (arr[i]==false){
                min = i;
                break;
            }
        }
        return index+1;
    }

    public void unreserve(int seatNumber) {
        arr[seatNumber-1] = false;
        if (seatNumber-1<min) min=seatNumber-1;
    }
}
